package LeetCode.interview;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

import LeetCode.interview._104_Maximum_Depth_of_Binary_Tree.TreeNode;

import sun.tools.jar.resources.jar;
import util.LogUtils;

/*
 * 
原题　
		Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.
	
	Note: You may not slant the container and n is at least 2. 
题目大意
	在二维坐标系中，(i, ai) 表示 从 (i, 0) 到 (i, ai) 的一条线段，任意两条这样的线段和 x 轴组成一个木桶，找出能够盛水最多的木桶，返回其容积。 
	http://www.jianshu.com/p/23e8e3e53abf
解题思路
	如果容器盛水最多

	    1.矩形面积最大。
	    2.盛水量的多少，由两条垂线中较短的一条决定。
	    3.两条垂线中较短一条尽可能长。
	//动图！！！
	http://www.jianshu.com/p/23e8e3e53abf
 * @Date 2017-10-06 23：57
 */
public class _011_Container_With_Most_Water {
	
	/**
	 * 感觉就是暴力法
	 * @param height
	 * @return
	 */
    public int maxArea(int[] height) {
    	int l = 0, r = height.length-1;
    	int maxArea = 0;
    	while (l < r) {
    		//木桶面积取决于短边
    		int area = Math.min(height[l], height[r])*(r-l);		//面积=高*底
    		if (area > maxArea) {
    			maxArea = area;
    		}
    		//尽可能让两边长度接近、越长越好
    		if (height[l] < height[r]){
    			l++;
    		} else {
    			r--;
    		}
    	}
        return maxArea;
    }
    
	public static void main(String[] args) {
		_011_Container_With_Most_Water obj = new _011_Container_With_Most_Water();
		obj.maxArea(new int[]{3, 2, 4});
	}

}
